#pragma once

#include <algorithm>
#include <vector>
#include <boost/unordered_map.hpp>
typedef size_t heap_id;

namespace details
{
  template<class K, class V>
  struct binary_heap_el_t
  {
    binary_heap_el_t(K key, V val, heap_id index) :
      key(key), value(val), index(index)
    {
    }
    K key;
    V value;
    heap_id index;
  };

  template<class K, class V>
  bool operator <(binary_heap_el_t<K, V> const & lhs,
                  binary_heap_el_t<K, V> const & rhs)
  {
    return lhs.key < rhs.key;
  }
}

template<class K, class V, class Compare = std::less<K> >
struct binary_heap_t
{
  typedef V value_type;
  typedef K key_type;
  typedef size_t size_type;

  binary_heap_t(Compare const & comp = Compare());
  binary_heap_t(size_type capacity, Compare const & comp = Compare());

  heap_id push(std::pair<K, V> const & el);
  heap_id push(K key, V val);
  std::pair<K, V> extract_top();
  void decrease_key(heap_id id, K new_key);
  bool empty() const
  {
    return heap_data_.empty();
  }
  size_type size() const
  {
    return heap_data_.size();
  }
private:
  typedef std::vector<details::binary_heap_el_t<K, V> > data_storage_t;
  typedef boost::unordered_map<heap_id, typename data_storage_t::size_type>
      index_storage_t;
  data_storage_t heap_data_;
  index_storage_t heap_index_;
  size_t last_id_;
  Compare comp_;

  void swap_elements(typename data_storage_t::size_type e1,
                     typename data_storage_t::size_type e2);
  void bubble_up(typename data_storage_t::size_type it);
  void sift_down(typename data_storage_t::size_type it);
  typename data_storage_t::size_type
  node_parent(typename data_storage_t::size_type it);
  typename data_storage_t::size_type
  node_lchild(typename data_storage_t::size_type it);
  typename data_storage_t::size_type
  node_rchild(typename data_storage_t::size_type it);
};

#include "binary_heap_impl.h"
